HDU_5773

题解

0可以转化成任意整数，包括负数，显然求LIS时尽量把0都放进去必定是正确的。因此我们可以把0拿出来，对剩下的做O(nlogn)的LIS，统计结果的时候再算上0的数量。为了保证严格递增，我们可以将每个权值S[i]减去i前面0的个数，再做LIS，就能保证结果是严格递增的。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdio>
using namespace std;
#define inf 0x3f3f3f3f
int n,zeronum;
int a[1000005],b[1000005],tmp[1000005],tt[1000005];
int work(){
    int cnt=0;
    for(int i=0 ; i <=n ;i++)
        tt[i] = inf ;
    int zerocnt=0;
    for(int i=1 ; i <= n; i++){
        if(a[i]){
            b[cnt]=a[i]-zerocnt;
            tmp[cnt++]=a[i]-zerocnt;
        }
        else zerocnt++;
        //数a[i]之前有多少零
    }
    //整个数组里有多少零
    zeronum = n - cnt;
    //离散化
    sort(tmp,tmp+cnt);
    int size = unique(tmp,tmp+cnt)-tmp;
    for(int i=0; i< cnt ; i++)
        b[i] = lower_bound(tmp,tmp+size,b[i]) - tmp + 1;
    tt[0] = -1; tt[1] = b[0];
    //LIS
    int lis=1, tk;
    for(int i=1; i < cnt ; i++){
        tk = lower_bound(tt,tt+size+1,b[i]) - tt ;
        tt[tk] = b[i];
        lis = max(lis, tk);
    }
    return lis;
}
int main(){
    int t;int tp=1;
    cin>>t;
    while(tp<=t){
        scanf("%d",&n);bool zero=1;
        int ans=0;
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            if(zero && a[i]) zero =0;
        }
        cout<<"Case #"<<tp++<<": ";
        if(zero)ans=n;
        else{
            int ll=work();
            ans=zeronum+ll;
        }
        printf("%d\n",ans);
    }
}